#! /usr/bin/env python
# -*- coding: utf-8 -*-
"""
@File Name: 图的检索的实现_gsearch.py
@Author: LT
@Date: 2021/9/29 15:54
# -----------------------------------------------------------------------------------------------------
@Description: 
这是基于深度优先的搜索
# -----------------------------------------------------------------------------------------------------
"""
Graph = {'A':  ['B', 'E', 'G'],
         'B':  ['C'],                        # 循环指向图，存储为字典，键指向各节点
         'C':  ['D', 'E'],
         'D':  ['F'],
         'E':  ['C', 'F', 'G'],
         'F':  [ ],
         'G':  ['A']}


def tests(searcher):                         # 测试搜索函数
    print(searcher('E', 'D', Graph))         # 查找'E' to 'D'之间所有路径
    for x in ['AG', 'GF', 'BA', 'DA']:
        print(x, searcher(x[0], x[1], Graph))


def search(start, goal, graph):
    solns = []
    generate([start], goal, solns, graph)               # 收集所有路径
    solns.sort(key=lambda x: len(x))                    # 按照路径长度排序
    return solns


def generate(path, goal, solns, graph):
    """重点在这个函数"""
    state = path[-1]
    if state == goal:                                   # 找到目标
        solns.append(path)                              # 原地改变solns
    else:                                               # 在这儿检查所有可能到达的节点
        for arc in graph[state]:                        # 记录已经访问过的节点从而，避免路径循环
            if arc not in path:
                generate(path + [arc], goal, solns, graph)


if __name__ == '__main__':
    tests(search)
    pass
